#include <iostream>
#include <limits.h>
#include <algorithm>
#include "SortTestHelper.h"
#include "Student.h"


using namespace std;

template<typename T>
void selectionSort(T arr[] , int n ){

    for(int i = 0 ; i < n ; i++){

        //寻找[i ,  n ] 区间里的最小值
        int minIndex = i ;
        for ( int j = i + 1 ; j < n ; j++){
            if ( arr[j] < arr[minIndex])
                minIndex = j ;
        }
        swap( arr[i] , arr[minIndex]);
    }

}

template <typename T>
void insertSort(T arr[], int n){

    for(int i = 0 ; i < n ; i++){


        for(int j=i ; j > 0 ; j--){

            //寻找元素arr[i]合适的位置
            if (arr[j]<arr[j-1]){
                swap(arr[j],arr[j-1]);
            }else{
                break;
            }
        }

//        for(int j=i ; j > 0&arr[j]<arr[j-1] ; j--){
//            //寻找元素arr[i]合适的位置
//                swap(arr[j],arr[j-1]);
//
//        }
    }



}

int main(){

    int n =10011;
    int *arr = SortTestHelper::generateRandomArray(n,0,n);
    int *arr2 = SortTestHelper::copyIntArray(arr,n);


    SortTestHelper::testSort("insertSort",insertSort,arr,n);
    SortTestHelper::testSort("selectSort",selectionSort,arr2,n);
    delete[] arr,arr2;

    return 0;


}


